Prior art signal switch architectures suffer from a number of limitations caused by the physical attributes of the data path and control. For instance, throughput per port generally decreases as the number of ports is increased. In addition, many prior art switches are not capable of handling gigabit per second port rates. Prior art switch architectures generally include variations on output-buffered, input-buffered, and shared memory architectures T. Takeuchi, H. Suzuki, and T. Aramaki, "Switch Architectures and Technologies for Asynchronous Transfer Mode," IEICE Transactions Vol. E 74, No. 4, April 1991; C. Partridge, Gigabit Networking, Addison-Wesley Publishing, 1994, Ch. 5, pp. 89-125!.
In a prior art output-buffered switch, such as that shown in FIG. 1, N inputs connect to each dedicated output buffer. Each input may send a signal to the switch in each time slot. The buffers are identical, but each is programmed to function as a unique output port and only accepts signals destined for that output See, e.g. M. J. Karol, M. G. Hluchyj, and S. P. Morgan, "Input Versus Output Queuing on a Space-Division Packet Switch," IEEE Transactions on Communications, Vol. 35, No. 12, December 1987, pp. 1347-1356; H. Suzuki, H. Nagano, T. Suzuki, T. Takeuchi, and S. Iwasaki, "Output-Buffer Switch Architecture for Asynchronous Transfer Mode," International Journal of Digital and Analog Cable Systems Vol. 2, pp. 269-276, 1989!. It is possible that as many as all N signals coming into the switch during a time slot may be destined for one buffer, requiring that each buffer must be able to accept N signals during any one time slot. Thus, while an output-buffered switch has excellent output characteristics because the output is read only once per time slot, it still encounters speed limitations because the number of write operations to the queue must equal the number of inputs.
In a prior aml input-buffered switch, such as that shown in FIG. 2, each of the N inputs is connected to a dedicated buffer. Signals are subsequently routed to the correct destination by passing through a circuit switch matrix See, e.g. M. J. Karol, et. al., Supra; N. Arakawa, A. Noiri, and H. Inoue, "ATM switch for Multi-Media Switching System," International Switching Symposium (ISS) '90, Vol. A 7 No. 2, May 1990!. Since only one signal can be written to a particular output port at a time, other signals destined for that output must remain in the buffers until the output is not busy. Only the first signal in a buffer can be read, so if it must wait for an output that is not busy, no other signals can leave the buffer. This is known as head-of-line (HOL) blocking. Therefore, it is possible that the buffer may need to be read N times per time slot in order to supply 100% flow to N outputs. Thus, while an input-buffered switch has excellent input characteristics, it still encounters speed limitations because the number of read operations per time slot must equal the number of outputs for 100% throughput.
A prior art shared memory switch, such as that shown in FIG. 3, uses a common memory to store cells from all N inputs. This is an efficient utilization of memory since active inputs can use the memory space of inactive inputs See, e.g. H. Kuwahara, N. Endo, M. Ogino, T. Kozaki, Y. Sakurai, and S. Gohara, "A Shared Buffer Memory Switch for an ATM Exchange," ICC '89, pp. 118-122, June 1989!. However, one of the limitations of this architecture is illustrated by events when N signals arrive in one time slot. This requires N separate writes to the memory, producing the same speed limitation as seen in an output-buffered architecture, since, again, per port speed is necessarily divided by N. Similarly, the shared memory must be read N times in order to supply signals to outputs in one time slot, producing the same speed limitation found in an input-buffered architecture. Thus, while a shared memory switch provides excellent queue efficiency, it has both the input speed limitations of the output-buffered switch and the output speed limitations of the input-buffered switch.
The prior art "Sunshine" switch, shown in FIG. 4, is essentially an output-buffered Batcher-Banyan network. A Batcher-Banyan network in general is a self-routing switch which performs the same routing functions as an externally controlled x-y space switch See, e.g. T. T. Lee, "Nonblocking Copy Networks for Multicast Packet Switching," IEEE Journal on Selected Areas in Communications, Vol.9, No. 9. 12-1988, pp. 1455-1467; H. Uematsu and R. Watanabe, "Architecture of a Packet Switch Based on Banyan Switching Network with Feedback Loops," IEEE Journal on SelectedAreas in Communications, Vol.9, No. 9. 12-1988, pp. 1521-1527!. It has the advantage of port expandability over an x-y space switch because the hardware required by an N-port Batcher-Banyan switch is roughly proportional to Nlog.sub.2 N rather than N.sup.2 for an N-port x-y space switch. On the other hand, the Batcher-Banyan has limited broadcasting capability and lower connectivity than the x-y space switch. The Batcher-Banyan network is often used to steer signals into a set of buffers, resulting in an essentially output-buffered architecture.
Several switch architectures have been developed utilizing a Batcher-Banyan network and signal feedback, including the "STARLITE" and "Sunshine" switches. The "STARLITE" switch is based on an input-buffered architecture A. Huang and S. Knauer, "STARLITE: A Wideband Digital Switch" Proc. IEEE Communications Society GLOBECOM84 (Atlanta, Ga.), 26-29 Nov. 1984, pp.121-125!, while the "Sunshine" switch shown in FIG. 4 is, except for the input-buffered recirculator queues, basically output-buffered J. N. Giacopelli, J. J. Hickey, W. S. Marcus, W. D. Sincoskie, and M. Littlewood, "Sunshine: A High Performance Self-Routing Broadband Packet Switch Architecture," IEEE Journal on Selected Areas in Communications, Vol. 9, No. 8, October 1991, pp. 1289-1298!. The most significant difference between these two approaches and the present invention is that they recirculate contending signals back through the circuit switch sorting network again during the very next switch cycle, regardless of whether the intended outputs have become not busy. This recirculation occurs solely within the circuit switch matrix and can occur repeatedly to a particular signal, leading to excessive latency that could cause loss of signal sequence integrity.
The present invention solves these problems by using a single merged buffer that is outside the circuit switch fabric to temporarily store both correctly and incorrectly routed cells. The cells are not repeatedly recirculated through the circuit switch matrix, but are instead misrouted for temporary storage and then sent immediately to the correct destination when the output port is no longer busy.